A Viterbi decoder is known from Tsui Chi-Ying, et al. “Low Power ACS Unit Design for the Viterbi Decoder” in IEEE Proceedings of the 1998 International Symposium on Circuits and Systems, ISCAS 1999, pages 137-140 Volume 1, which contains a branch metric calculation circuit for calculation of branch metrics, a path metric calculation circuit for calculation of path metrics as a function of the branch metrics, and a selection circuit, in order that the path which has the optimum path metric is selected from the temporarily stored path metrics.
JP 2000059238 describes a code synchronization decision circuit for a Viterbi decoder, in which the selection is carried out using an adjustable threshold value.
DE 197 42 958 A1 describes a coprocessor for provision of auxiliary functions for a Viterbi decoding method.
A Viterbi decoder is likewise known from Shieh Ming-Der et al “Efficient Management of In-Place Path Metric Update and its Implementation for Viterbi Decoders IN” IEEE Proceedings of the 1998 International Symposium on Circuits and Systems, ISCAS 1998, pages 449-452 Volume 4, which has a branch metric calculation circuit, a path metric calculation circuit and a selection circuit.
Shung, C. B. “VLSI architectures for metric normalization in the Viterbi algorithm IN” IEEE International Conference on Communications, 1990. ICC 1990, Including Supercomm Technical Sessions. SUPERCOMM/ICC 1990. Conference Record., 1990, pages 1723-1728 Volume 4 describes techniques for normalization of the path metrics.
Viterbi decoders are used for decoding what are referred to as convolution codes. During this decoding process, the received data sequence is compared continuously with theoretically possible transmission data sequences, and the level of the match is used as the basis for a decision, by means of a statistical calculation method. Viterbi decoders are used in most conventional digital mobile radio receivers. A Viterbi decoder is what is referred to as a maximum likelihood decoder, which is generally used for decoding channel-coded, in particular convolutional-coded, mobile radio or cable-based telecommunications signals.
FIG. 1 shows a transmitter and a receiver, which contains a Viterbi decoder according to the prior art. Within the transmitter, a signal source produces data symbols, which are supplied to a convolutional coder. The convolutional-coded transmission data symbols are modulated in a modulator and are supplied via any given transmission channel to the receiver. Only the received signal is demodulated in a demodulator in the receiver, and is then equalized. The received data symbols are decoded in a Viterbi decoder which is contained in the receiver, and are emitted to a data sink for further data processing.
During the channel coding process, redundant information is added in the transmitter to the data symbols to be transmitted, in order to improve the transmission reliability. During the transmission process via a telecommunications channel, the transmitted signal has noise superimposed on it. The receiver uses the received data symbol sequence to extract from all the possible data transmission signals that data transmission sequence which has the highest probability of corresponding to the actually transmitted sequence.
The coding rule which is used for coding can be described by a corresponding trellis diagram. The Viterbi decoder contained in the receiver calculates what are referred to as metrics in order to determine that path in the trellis diagram which has the highest or the lowest path metric depending on the configuration of the Viterbi decoder. The Viterbi decoder uses this selected optimum path to determine the decoded data sequence, and to pass it to the data sink.
The metrics are preferably calculated on the basis of a telecommunications channel which is governed by additive white noise with a Gaussian distribution.
By way of example, FIG. 2 shows a trellis diagram with in each case four different states at the various times to t+3. The states correspond, for example, to the bit states 00, 10, 01, 11. Each data symbol sequence in the trellis diagram illustrated in the figure has a corresponding associated path. A path in this case comprises a sequence of branches between two successive states. In this case, each branch symbolizes a state transition between two successive states, in which case, for a code configured as shown in FIG. 2, the upper branch which originates from one state generally corresponds to a received data symbol with the binary value 0, and the lower branch which originates from the same state corresponds to a received symbol with the binary value one. Each of these state transitions, to which a branch metric λt is assigned, corresponds to a code symbol.
The branch metric λt is defined for Gaussian, white noise as follows:λt=|Yt−Rt|2  (1)where Rt is a received symbol at the time t, and Yt is a transmission signal expected as a function of this at the time t.
Furthermore, each path is assigned a path metric γt by the trellis diagram at the time t. This is defined as the sum of the branch metrics for a path
                              γ          t                =                                            ∑                              -                ∞                            i                        ⁢                          λ              i                                =                                    ∑                              -                ∞                            t                        ⁢                                                                                                Y                    t                                    -                                      R                    t                                                                              2                                                          (        2        )            
This calculation rule obviously contains the following recursion:γt=γt-1+λt  (3)
The Viterbi decoder contained in the receiver and illustrated in FIG. 1 uses the trellis diagram to determine that path which has the best path metric. By definition, this is generally the path with the lowest path metric. In the illustrated embodiment of a Viterbi decoder, this corresponds to the summed Euclidean distance. This path is that path which has the highest probability of having been transmitted.
The path metric of a path λts which leads to a specific state s is composed of the path metric γt−1s′ of a previous state and the branch metric λts′→s of the branch which leads from this previous state s′ to the specific state s. There is therefore no need for all possible paths and path metrics in the trellis diagram to be determined and evaluated by the Viterbi decoder. In fact, that path which has the best path metric prior to this time and prior to this state is determined for each state and for each time step in the trellis diagram. This is the only path which is temporarily stored, and the calculation process continues with the path metric of the partial winner path which opens into this state. All other paths which lead to this state are ignored. During each time step, there are thus a number of such paths corresponding to the number of different states NTS. The recursive calculation rule for the path metrics is in the form of a path metric calculation circuit, or an add/compare select unit (ASCU), within the Viterbi decoder.
FIG. 3 shows a Viterbi decoder according to the prior art. The Viterbi decoder as is illustrated in FIG. 3 contains a branch metric calculation circuit (BMU: Branch Metric Unit), a path metric calculation circuit (ASCU: Add-Compare-Select-Unit) and a selection circuit (SMU: Survivor Memory Unit). The branch metric calculation circuit BMU calculates the branch metrics λt(s), which are a measure of the difference between a received data symbol and that data symbol which causes the corresponding state transition in the trellis diagram. The branch metrics calculated by the branch metric calculation circuit BMU are supplied to the path metric calculation circuit ASCU in order to calculate the optimum paths and winner paths. The downstream selection circuit SMU stores the winner paths in a memory. Decoding is then carried out on the basis of that winner path which has the best path metric. The data symbol sequence associated with this path has the greatest probability of corresponding to the actually transmitted data sequence.
FIG. 4 shows the path metric calculation circuit ASCU contained in the conventional Viterbi decoder in detail. The path metric calculation circuit receives the calculated branch metrics from the branch metric calculation circuit BMU, and evaluates them. The evaluation is in this case carried out by means of various path metric calculation elements or processor elements PE. Depending on the version of the code, the ASCU processor element makes a decision between two or more competing paths which open into one state in the trellis diagram. The path with the better calculated metric is selected, and the path metric of the winner path which leads to this state is renewed.
FIG. 5 shows an ASCU processor element or path metric calculation element according to the prior art. The processor element contains two adders, whose outputs are connected to a multiplexer and to a comparator circuit. The first adder calculates the path metric of a first path, and the second adder calculates the path metric of a second path in the trellis diagram. The two path metrics are supplied to a comparator, where they are compared. The comparator emits a control signal to the multiplexer, and passes on the winner path, that is to say by definition the path with the lower path metric. The calculated path metric is temporarily stored by an associated downstream memory element, for example a register R, for the next calculation step.
The trellis diagram illustrated in FIG. 2 is a trellis diagram with what is referred to as a butterfly structure. This means that two states of a time step t+1 in the trellis diagram are in each case associated with two states from the previous time step t whose branches in each case lead to the first-mentioned states for the time step t+1. In this case, two branch metrics of the branches which originate from different states are in each case identical. In general, γt(s) denotes the path metric which is associated with the state s in the time step t, while λt(s) denotes the branch metric of the state transition, which corresponds to the signal s, at the time t. In the Viterbi decoder according to the prior art, two path metric calculation elements of the ACSU are combined in order to form a butterfly path metric calculation element. The advantage is that the path metrics for each state relating to the time index t−1 need be read only once with preferably sequential implementation of the ACSU. Process or elements configured in this way behave in the same way as conventional Add-Compare-Select processor elements, with the only difference being that they calculate two states of the trellis diagram at the same time.
Since the path metric calculation rule, by virtue of the recursion, represents a sum of the time index t′=−∞ . . . t (see equation 2), overflowing of the path metrics must be prevented by what is referred to as a normalization circuit. The minimum normalization method is preferably used for this refinement of the Viterbi decoder. In this case, the minimum path metric for the time index t−1 is determined and is subtracted equally from all the winner path metrics for the time index t. With this method, precisely the noise component of the received signal Rt is subtracted, statistically on average.
The comparison results δs calculated by the various processor elements PE are emitted to the downstream selection circuit SMU for selection of the correct winner path.
The disadvantage of the Viterbi decoder illustrated in FIG. 4 and according to the prior art is that all the decision values δs for selection of the winner path must be stored together with the optimum path metric in the memory of the selection circuit SMU. The number of decisions δs which must be stored in this case corresponds to the number NTS of states in the trellis code. Thus, with the Viterbi decoder illustrated in FIG. 4 and according to the prior art, NTS decisions are stored in the selection circuit SMU for each symbol time step. This storage process is highly redundant, since the decoder requires only the decision for one state per time index t in order in the end to reconstruct the winner path and hence the decoded data symbols.
Depending on the embodiment of the Viterbi decoder, the memory accesses dominate the power loss. The power loss Pv caused by writing all the decision values δs from the path metric calculation circuit to the selection circuit SMU is thus very high. When using a Viterbi decoder, for example, in a mobile radio, the operating life is shortened by discharging the batteries more quickly. Furthermore, for example in multichannel telecommunications systems such as ADSL and SDSL, the high power loss leads to an undesirable amount of heating being produced.